1. Field of the Invention
The present invention relates generally to turbo decoding apparatus, and more particularly to a soft-output decoder that decodes a received data stream by making soft decisions.
2. Description of the Related Art
FIG. 19 shows the general structure of a turbo code transmission system. The system includes a turbo coder 100, a modulator (MOD) 200, a communication channel (CHNL) 300, a demodulator (DEMOD) 400, and a turbo decoder 500.
The turbo coder 100 includes a first recursive systematic convolutional coder 101a, a second recursive systematic convolutional coder 101b, and an interleaver 102. The input data Din of the turbo coder 100 are binary data. The turbo coder 100 has, for example, a coding rate of ⅓ and a constraint length of four.
When a data stream Din is supplied, since the coding rate is ⅓, the turbo coder 100 outputs three data streams X1, Y1, Y2. Output data stream X1 is identical to the input data stream Din. Output data stream Y1 is obtained by the first recursive systematic convolutional coder 101a from the input data stream Din. Output data stream Y2 is obtained by the second recursive systematic convolutional coder 101b from an interleaved data stream supplied by the interleaver 102. The interleaver 102 receives the input data stream Din and rearranges the data sequence according to a fixed procedure, thereby generating the interleaved data stream.
The first and second recursive systematic convolutional coders 101a, 101b have the same internal structure. This structure is shown in FIG. 20, in which reference numeral 101 designates either the first recursive systematic convolutional coder 101a or the second recursive systematic convolutional coder 101a or the second recursive systematic convolutional coder 101b. 
Since the constraint length is four, the recursive systematic convolutional coder 101 comprises a shift register with three register cells 111, 112, 113. The recursive systematic convolutional coder 101 also comprises four exclusive-OR logic circuits 114, 115, 116, 117. Initially, the register cells 111, 112, 113 are all cleared. As each bit of the input data stream Din is received at the input terminal IN, exclusive-OR logic circuit 117 takes the exclusive logical OR of the output of register cells 112 and 113; exclusive-OR logic circuit 114 then takes the exclusive logical OR of the output of exclusive-OR logic circuit 117 and the input data bit from the input data stream Din; exclusive-OR logic circuit 115 takes the exclusive logical OR of the output of exclusive-OR logic circuit 114 and the first register cell 111; and exclusive-OR logic circuit 116 takes the exclusive logical OR of the output of exclusive-OR logic circuit 115 and the third register cell 113. The output of exclusive-OR logic circuit 116 is output from an output terminal (OUT) as the coded bit Y1 or Y2. Then the output of exclusive-OR logic circuit 114 is shifted into register cell 111 while the output of register cell 111 is shifted into register cell 112 and the output of register cell 112 is shifted into register cell 113. The new contents of the register cells become the outputs of the register cells, and the above process is repeated on the next bit of input data.
The shift register comprising register cells 111, 112, 113 has eight states, depending on whether the output of each register cell is ‘0’ or ‘1’. From each state, a transition can occur to just two other states, according to the value of the input bit.
In FIG. 19, the modulator 200 modulates the three data streams (transmit data streams) X1, Y1, Y2 received from the turbo coder 100, by quadrature phase shift-keying (QPSK), for example, and sends the modulated streams to the communication channel 300. When the transmitted signals reach the demodulator 400, they include noise acquired in the communication channel 300.
The demodulator 400 demodulates the received signals by the reverse of the process performed by the modulator 200, and outputs received data streams X1′, Y1′, Y2′, which correspond to transmitted data streams X1, Y1, Y2, respectively, but include noise. The received data streams X1′, Y1′, Y2′ may comprise multi-valued (ternary or higher-valued) data.
FIG. 21 is a block diagram illustrating the structure of a conventional turbo decoder, comprising a pair of conventional soft-output decoders 501a, 501b, a pair of interleavers 51, 52, a pair of deinterleavers 53, 54, a selector 55, and a hard decision unit 56.
The turbo code transmission system shown in FIG. 19 and the conventional turbo decoder shown in FIG. 21 are disclosed in Nikkei Electronics 721 (Jul. 13, 1998), pages 163 to 177.
In the conventional turbo decoder shown in FIG. 21, the (noisy) received data stream X1′ is input to both the first soft-output decoder 501a and interleaver 51, the (noisy) received data stream Y1′ is input to the first soft-output decoder 501a, and the (noisy) received data stream Y2′ is input to the second soft-output decoder 501b. 
The first soft-output decoder 501a outputs an extrinsic information likelihood stream Leout-a to interleaver 52, and the second soft-output decoder second soft-output decoder 501b outputs an extrinsic information likelihood stream Leout-b to deinterleaver 53. Interleaver 51 interleaves received data stream X1′ and outputs the interleaved stream to the second soft-output decoder 501b. Interleaver 52 outputs an a-priori information likelihood stream Lin-b, which is an interleaved stream corresponding to extrinsic information likelihood stream Leout-a, to soft-output decoder 501b. Deinterleaver 53 outputs an a-priori information likelihood stream Lin-a, which is a deinterleaved stream corresponding to extrinsic information likelihood stream Leout-b, to the first soft-output decoder 501a. 
In addition, soft-output decoder 501a outputs a soft-decision data stream Lout-a to the selector 55, and soft-output decoder 501b outputs a soft-decision data stream Lout-b output to deinterleaver 54. Deinterleaver 54 outputs a deinterleaved version of soft-decision data stream Lout-b to the selector 55; the selector 55 outputs a selected data stream to the hard decision unit 56; the hard decision unit 56 outputs a turbo-decoded data stream Dout, which corresponds to the transmitted data stream Din (see FIG. 19).
The operation of the conventional turbo decoder shown in FIG. 21 will now be described. The interleavers 51, 52 have the same structure as the interleaver 102 in the turbo coder 100 shown in FIG. 19. Interleaver 51 rearranges the data sequence of data stream X1′ according to a fixed procedure and outputs the interleaved stream to the second soft-output decoder 501b. Interleaver 52 rearranges the data sequence of extrinsic information likelihood stream Leout-a according to the same procedure as used in interleaver 51 and outputs a-priori information likelihood stream Lin-b to the second soft-output decoder 501b. 
The deinterleavers 53, 54, which both have the same internal structure, restore the interleaved data streams to their original sequence. Deinterleaver 53 deinterleaves the data sequence of extrinsic information likelihood stream Leout-b by performing the reverse of the process performed by interleaver 51 or interleaver 52, and outputs a-priori information likelihood stream Lin-a to the first soft-output decoder 501a. Deinterleaver 54 deinterleaves the data sequence of soft-decision data stream Lout-b by the same procedure as used in deinterleaver 53 and outputs the deinterleaved stream to the selector 55.
The first soft-output decoder 501a uses the (noisy) data streams X1′ and Y1′ to perform calculations that estimate the transmitted data stream X1. (Din), and outputs the soft-decision data stream Lout-a and extrinsic information likelihood stream Leout-a, which are obtained as results of these calculations. The a-priori information likelihood stream Lin-a is also input to the first soft-output decoder 501a. In the first iteration of the soft-decision decoding process, however, soft-output decoder 501a does not use the a-priori information likelihood stream Lin-a because the initial values thereof are all ‘0’.
The second soft-output decoder 501b uses the interleaved (noisy) data stream X1′, the (noisy) data stream Y2′, and the a-priori information likelihood stream Lin-b obtained by interleaving the extrinsic information likelihood stream Leout-a to perform calculations that estimate the interleaved transmitted data stream X1 (Din), and outputs the soft-decision data stream Lout-b and extrinsic information likelihood stream Leout-b, which are obtained as results of these calculations.
The first soft-output decoder 501a now uses the (noisy) data stream X1′, (noisy) data stream Y1′, and a-priori information likelihood stream Lin-a obtained by deinterleaving the extrinsic information likelihood stream Leout-b to repeat the soft-decision decoding calculations that estimate the transmitted data stream X1 (Din), and outputs the resulting soft-decision data stream Lout-a and extrinsic information likelihood stream Leout-a.
The second soft-output decoder 501b then uses the interleaved data stream X1′, data stream Y2′, and the a-priori information likelihood stream Lin-b obtained by interleaving the recalculated extrinsic information likelihood stream Leout-a output from the first soft-output decoder 501a to repeat the soft-decision decoding calculations that estimate the interleaved transmitted data stream X1 (Din), and outputs the resulting soft-decision data stream Lout-b and the extrinsic information likelihood stream Leout-b.
The soft-output decoders 501a, 501b iterate the soft-decision decoding process described above a prescribed number of times.
When the soft-output decoders 501a, 501b have finished the prescribed number of iterations of the soft-decision decoding process, the selector 55 selects either the soft-decision data stream Lout-a output from the first soft-output decoder 501a or the deinterleaved soft-decision data stream Lout-b output from deinterleaver 54, and outputs the selected soft-decision data stream to the hard decision unit 56.
The hard decision unit 56 uses the selected soft-decision data stream to make a hard decision (binary 0 or 1) at each bit position in the transmitted data stream X1 (Din)., and outputs the resulting binary data stream as a decoded data stream Dout, which is the output of the turbo decoder.
FIG. 22 illustrates the data sequences of the following data streams transmitted and received in the turbo code transmission system X1 (transmitted data stream input to the first recursive systematic convolutional coder 101a), X1-interleaved (transmitted data stream output from the interleaver 102 and input to the second recursive systematic convolutional coder 101b), Y1 (transmitted data stream output from the first recursive systematic convolutional coder 101a), Y2 (transmitted data stream output from the second recursive systematic convolutional coder 101b), X1′ (received data stream input to soft-output decoder 501a), X1′-interleaved (received data stream output from interleaver 51), Y1′ (received data stream input to soft-output decoder 501a), Y1′-interleaved (virtual stream, because the received data stream Y1′ is not input to an interleaver), Y2′ (received data stream input to soft-output decoder 501b), and Y2′interleaved (virtual stream, because the received data stream Y2′ is not input to an interleaver). For brevity, each data stream has four data elements in four positions k1, k2, k3, k4, which are decoding positions in the received data stream.
Data stream X1, the transmitted data stream input to the first recursive systematic convolutional coder 101a, has data elements x1, x2, x3, x4 in positions k1, k2, k3, k4, respectively. The data elements x1, x2, x3, x4 are input to the first recursive systematic convolutional coder 101a in that order.
Data stream Y1, the transmitted data stream output from the first recursive systematic convolutional coder 101a, has data elements y1, y2, y3, y4 in positions k1, k2, k3, k4, respectively.
Data stream X1-interleaved, the transmitted data stream output from the interleaver 102, has, for instance, data elements x3, x1, x4, and x2 in positions k1, k2, k3, k4, respectively. This interleaving sequence is only one of the various possible interleaving sequences that may be used. The data elements x3, x1, x4, and x2 of this data stream x1-interleaved are input to the second recursive systematic convolutional coder 101b in the interleaved order.
Data stream Y2, the transmitted data stream output from the second recursive systematic convolutional coder 101b, has data elements z3, z1, z4, and z2 in positions k1, k2, k3, k4 respectively.
Data stream X1′, the received data stream corresponding to the transmitted data stream X1 and input to soft-output decoder 501a, has data elements x1′, x2′, x3′, x4′, corresponding to transmitted data elements x1, x2, x3, x4, in positions k1, k2, k3, k4, respectively.
Data stream Y1′, the received data stream corresponding to transmitted data stream Y1 and input to soft-output decoder 501a, has data elements y1′, y2′, y3′, y4′, corresponding to transmitted data elements y1, y2, y3, y4, in positions k1, k2, k3, k4, respectively.
Data stream X1′-interleaved, the received data stream output from interleaver 51 and input to soft-output decoder 501b, has, for instance, data elements x3′, x1′, x4′, x2′ in positions k1, k2, k3, k4, respectively, matching the interleaving sequence used by interleaver 102.
Data stream Y1′-interleaved, which is a virtual received data stream that would be output from interleaver 51 if interleaver 51 received data stream Y1′, has data elements y3′, y1′, y4′, y2′ in positions k1, k2, k3, k4, respectively.
Data stream Y2′, the received data stream corresponding to transmitted data stream Y2 and input to soft-output decoder 501b, has data elements z3′, z1′, z4′, z2′, corresponding to transmitted data elements z3, z1, z4, z2, in positions k1, k2, k3, k4, respectively.
Data stream Y2′-deinterleaved, which is a virtual received data stream that would be output from deinterleaver 53 if deinterleaver 53 received data stream Y2′, has data elements z1′, z2′, z3′, z4′ in positions k1, k2, k3, k4, respectively.
The a-priori information likelihood stream Lin-a input to soft-output decoder 501a and the soft-decision data stream Lout-a and extrinsic information likelihood stream Leout-a output from soft-output decoder 501a have data sequences associated with the data streams X1, Y1′, and Y2′-deinterleaved. In decoding position k1, for instance, the a-priori information likelihood stream Lin-a has the a-priori likelihood values of received data elements x1′, y1′, and z1′.
The a-priori information likelihood stream Lin-b input to soft-output decoder 501b and the soft-decision data stream Lout-b and extrinsic information likelihood stream Leout-b output from soft-output decoder 501b have data sequences associated with the data streams X1′-interleaved, Y1′-interleaved, and Y2′. In decoding position k1, for instance, the a-priori information likelihood stream Lin-b has the a-priori information likelihood values of received data elements x3′, y3′, and z3′.
FIG. 23 is a flowchart illustrating the soft-decision decoding algorithm, referred to as the maximum a-posteriori probability (MAP) decoding algorithm.
In step S2, the received data stream Xin (X1′ or X1′interleaved in FIG. 21), the received data stream Yin (Y1′ or Y2′ in FIG. 21), and the a-priori information likelihood stream Lin (Lin-a or Lin-b in FIG. 21) are used to compute branch metric values (also referred to below as branch metrics). In the first soft-decision decoding process, the received data streams Xin and Yin are used for the branch metric computation. The branch metric computations are performed sequentially for each position in the data streams. The branch metrics indicate the probability of existence of state transition paths resulting from data input to the turbo coder.
In step S3, the branch metrics obtained in step S2 are used to compute forward state metrics by recursion. These computations are also performed sequentially for each position in the data streams. The forward state metrics, also referred to below as forward recursion state metrics or forward recursion state metric values, indicate the probability of existence of each state encountered when paths are traced forward in time on the basis of the branch metrics.
In step S4, the branch metrics obtained in step S2 are used to compute backward state metrics by recursion. These computations are also performed sequentially for each position in the data stream. The backward state metrics, also referred to below as backward recursion state metrics or backward recursion state metric values, indicate the probability of existence of each state found when paths are traced backward in time on the basis of the branch metrics.
In step 55, the branch metrics obtained in step S2 and the state metrics obtained in steps S3 and S4 are used to perform a soft-decision computation for each decoding position in the transmitted data stream X1 (Din in FIG. 19), and the soft-decision data stream obtained by these computations is output.
In the flowchart shown in FIG. 23, the forward recursion state metric computations are performed before the backward recursion state metric computations. The MAP decoding algorithm allows the forward recursion state metric computations and the backward recursion state metric computations to be performed in the reverse order, however, or to be performed simultaneously (in parallel).
FIG. 24 is a block diagram illustrating the structure of a conventional soft-output decoder 501 (the first soft-output decoder 501a or second soft-output decoder 501b in FIG. 21). Input data stream Xin in FIG. 24 corresponds to X1‘or X1′-interleaved in FIG. 21. Input data stream Yin corresponds to Y1′ or Y2′ in FIG. 21. A-priori information likelihood stream Lin corresponds to Lin-a or Lin-b in FIG. 21. The extrinsic information likelihood stream Leout corresponds to Leout-a or Leout-b in FIG. 21. The soft-decision data stream Lout corresponds to Lout-a or Lout-b in FIG. 21.
The conventional soft-output decoder 501 comprises a branch metric computation (COMP.) unit 511, a likelihood RAM 12, a branch metric RAM 13, a forward recursion state metric (FRSM) computation unit 516f, a backward recursion state metric (BRSM) computation unit 516r, a forward recursion state metric RAM 17f, a backward recursion state metric RAM 17r, a soft-decision computation (SDC) unit 18, and a differential (DIFF.) computation unit 19.
The operation of the conventional soft-output decoder 501 shown in FIG. 24 will now be described. The soft-decision decoding process is carried out on a data stream equal in length to a positive integer n, comprising data elements in the first to n-th positions.
The branch metric computation unit 511 uses the input received data streams Xin and Yin and, except in the first soft-decision decoding iteration, the a-priori information likelihood stream Lin to sequentially perform branch metric computations at corresponding positions in the data streams (this step corresponds to step S2 in FIG. 23), and writes the branch metric values obtained by the computations into the branch metric RAM 13. At the same time, the branch metric computation unit 511 obtains information likelihood values by adding a communication channel value to the a-priori information likelihood at each position of the data stream, and writes the information likelihood values thus obtained in the likelihood RAM 12.
The forward recursion state metric computation unit 516f reads the necessary branch metric values from the branch metric RAM 13, uses them to sequentially perform forward recursion state metric computations for corresponding positions in the data stream (this step corresponds to step S3 shown in FIG. 23), and writes the forward recursion state metrics thus obtained in the forward recursion state metric RAM 17f. 
The backward recursion state metric computation unit 516r reads the necessary branch metric values from the branch metric RAM 13, uses them to sequentially perform backward recursion state metric computations for corresponding positions in the data streams (this step corresponds to step S4 shown in FIG. 23), and writes the backward recursion state metrics thus obtained in the backward recursion state metric RAM 17r. 
The soft-decision computation unit 18 reads the necessary branch metric values and forward and backward recursion state metric values from the branch metric RAM 13, forward recursion state metric RAM 17f, and backward recursion state metric RAM 17r, uses them to perform soft-decision computations for the corresponding positions in the data stream, and outputs the soft-decision data stream Lout thus obtained to the differential computation unit 19. This soft-decision data stream Lout is also output to the selector 55 or deinterleaver 54 shown in FIG. 21, as the output of the soft-output decoder, and is used for hard-decision computations.
The differential computation unit 19 reads necessary information likelihood values from the likelihood RAM 12, obtains extrinsic information likelihood values by calculating the difference between the information likelihood read from the likelihood RAM 12 and the soft-decision data input from the soft-decision computation unit 18 for each position of the data streams, and outputs the extrinsic information likelihood stream Leout. This extrinsic information likelihood stream Leout is input to interleaver 52 or deinterleaver 53 (FIG. 19), which supplies the a-priori information likelihood stream Lin to the next-stage soft-output decoder (that is, to the other soft-output decoder in FIG. 19).
The conventional soft-output decoder used in turbo decoding accordingly has to perform a great number of computations to calculate the existence probabilities of each state. The turbo decoder iterates the soft-output decoding computations, feeding the likelihood values obtained from each iteration into the next iteration, so the series of computations is repeated a number of times; the number of repetitions is conventionally predetermined according to the signal-to-noise ratio of the communication channel. These repeated computations consume power and take time. For a transmission block with a high signal-to-noise ratio, many of the repetitions may be unnecessary, so much time and power are wasted.